package com.fw.leetcode.recursion;

import com.fw.leetcode.LeetCode;

import java.math.BigDecimal;
import java.math.RoundingMode;

/**
 * 50. Pow(x, n)
 *
 * Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
 *
 * Example 1:
 *  Input: x = 2.00000, n = 10
 *  Output: 1024.00000
 *
 * Example 2:
 *  Input: x = 2.10000, n = 3
 *  Output: 9.26100
 *
 * Example 3:
 *  Input: x = 2.00000, n = -2
 *  Output: 0.25000
 *  Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25
 *
 * Constraints:
 *  -100.0 < x < 100.0
 *  -2^31 <= n <= 2^31-1
 *  n is an integer.
 *  Either x is not zero or n > 0.
 *  -10^4 <= x^n <= 10^4
 */
public class Num_0050 implements LeetCode {
    private interface Solution {
        double myPow(double x, int n);

        default void assertEquals(double x, int n, double expected) {
            double result = BigDecimal.valueOf(myPow(x, n)).setScale(5, RoundingMode.HALF_UP).doubleValue();
            if (Double.compare(result, expected) != 0) {
                myPow(x,n);
            }
        }
    }

    private static class MyRecursionSolution implements Solution {

        @Override
        public double myPow(double x, int n) { // 其次：快速幂 + 递归：时O(log n) 空O(log n)
            /*
             * 快速幂 + 递归
             * O(log n)，单纯递归就需要 O(n)
             *
             * 特例 n = Integer.MIN_VALUE 时，-n 将溢出 = Integer.MIN_VALUE 仍是负数
             * 需将 int 扩展成 long 存储
             *
             * 2^8 = (2^4)^2 = ((2^2)^2)^2 => 共 3 次，不需要 8 次
             * 2^9 = (2^4)^2 * 2 = ((2^2)^2)^2 * 2
             * 2^-8 = (2^-4)^2 = ((2^-2)^2)^2
             */
            return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long) n); // 负数取正
        }

        private double quickMul(double x, long n) { // 此处入参 n 都为 long 型正数，避免溢出
            if (n == 0) return 1.0;
            double y = quickMul(x, n / 2); // n / 2 有奇有偶
            return n % 2 == 1 ? x * y * y : y * y;
        }
    }

    private static class MyIteratorSolution implements Solution {

        @Override
        public double myPow(double x, int n) { // 最优：快速幂 + 迭代：时O(log n) 空O(1)
            /*
             * 快速幂 + 迭代（烧脑）
             *
             * 特例 n = Integer.MIN_VALUE 时，-n 将溢出 = Integer.MIN_VALUE 仍是负数
             * 需将 int 扩展成 long 存储
             *
             * 设 i 从 1 开始追赶 77
             * x^77 = x^64 * x^13           =>  77 = 64 + 13 此时 i=64 为最大贡献值，再大就超过，剩余的 13 次需要再拆分
             *      = x^64 * x^8 * x^5      =>  13 = 8 + 5
             *      = x^64 * x^8 * x^4 * x  =>  5 = 4 + 1
             * 77 的二进制 0100 1101 各个1代表 64, 8, 4, 0
             * 从二进制第0位开始向高位遍历，将会依次计算
             *    x, x^2, x^4, x^8, x^16, x^32, x^64
             *    |       |    |                |
             * 1  r*      r*   r*               r*   -> r
             * 其中，当计算到77的二进制位为1的时候，将值乘到结果中去，最终 r 即为所求
             */
            return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long) n); // 负数取正
        }

        private double quickMul(double x, long n) { // 此处入参 n 都为 long 型正数，避免溢出
            double result = 1.0;
            // 依次计算 x 的幂次，从 0, 2, 4, 8, 16, 32, 64 .. 次幂
            double xPower = x;
            // 依次从 n 的二进制第0位向高位遍历
            while (n > 0) {
                // 判断第 0 位是否为1，需要乘到结果中去
                if ((n & 0x1) == 1) {
                    result *= xPower;
                }
                // x 的幂次进行平方
                xPower *= xPower;
                // 右移一位，去除前一个第0位
                n >>= 1;
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyIteratorSolution();
        solution.assertEquals(2.00000, 10, 1024.00000);
        solution.assertEquals(2.10000, 3, 9.26100);
        solution.assertEquals(2.00000, -2, 0.25000);
        solution.assertEquals(2.00000, Integer.MIN_VALUE, 0.0); // 溢出测试
    }
}
